//
//  Problem268.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/16.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 268. 丢失的数字 简单
 
 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

 示例 1：
     输入：nums = [3,0,1]
     输出：2
     解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
 示例 2：
     输入：nums = [0,1]
     输出：2
     解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
 示例 3：
     输入：nums = [9,6,4,2,3,5,7,0,1]
     输出：8
     解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
 示例 4：
     输入：nums = [0]
     输出：1
     解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
  
 提示：
 n == nums.length
 1 <= n <= 104
 0 <= nums[i] <= n
 nums 中的所有数字都 独一无二

 进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
 */
class Problem268: NSObject {
    /*
      方法一：异或
      异或：2个相同的数字执行异或 = 0；
      数组nums中却少一个数字，那么再把0～n中每一个数字都增加到数组中, 这样数组中缺少的那个数字只有1个，其他数字都是2个
      这样遍历数组中每个数字，依次执行异或，最后得到的就是缺少的那个数字
     */
    func missingNumber(_ nums: [Int]) -> Int {
        var xor = 0
        for (i, n) in nums.enumerated() {
            xor ^= i ^ n
        }
        xor ^= nums.count
        return xor
    }
    /*
      方法二：求和
      求和公式: sum = n(n+1)/2
      那么遍历数组nums；用sum - n,最后得到就是缺少的数字
     */
    func missingNumber1(_ nums: [Int]) -> Int {
        var sum = (nums.count * (nums.count + 1)) / 2
        for n in nums {
            sum -= n
        }
        return sum
    }
}
